import java.util.Random;

public class Solution {
    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    public void sortColors(int[] nums) {
        int left=-1,right=nums.length,cur=0;
        while(cur<right){
            if(nums[cur]==0) swap(nums,++left,cur++);
            else if(nums[cur]==1) cur++;
            else swap(nums,--right,cur);
        }
    }


    public int[] sortArray(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        // 1. 建堆（大顶堆）
        createHeap(array);
        // 2. 循环删除堆顶元素
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, 0, i);
            shiftDown(array, 0, i);  // 注意这里传入的end是未排序部分的长度
        }
        return array;
    }

    private void shiftDown(int[] array, int parent, int end) {
        int child = parent * 2 + 1;
        while (child < end) {
            // 选择较大的子节点（大顶堆）
            if (child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }
            if (array[parent] >= array[child]) {
                break;
            }
            swap(array, parent, child);
            parent = child;
            child = parent * 2 + 1;
        }
    }

    private void createHeap(int[] array) {
        // 从最后一个非叶子节点开始调整
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
    }


    public int[] sortArray2(int[] array) {
        qsort(array,0,array.length-1);
        return array;
    }

    public void qsort(int[] nums,int l,int r){
        if(l>=r) return;
        //数组分三块
        int key=nums[new Random().nextInt(r-l+1)+l];
        int left=l-1,right=r+1,cur=l;
        while(cur<right){
            if(nums[cur]<key) swap(nums,++left,cur++);
            else if(nums[cur]==key) cur++;
            else swap(nums,--right,cur);
        }

        qsort(nums,l,left);
        qsort(nums,right,r);
    }
}
